<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xml:lang="en" lang="en">
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Structure and Interpretation of Computer Programs, 2e: 2.5</title>

<meta name="description" content="Structure and Interpretation of Computer Programs, 2e: 2.5" />
<meta name="keywords" content="Structure and Interpretation of Computer Programs, 2e: 2.5" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="Generator" content="texi2any" />
<meta charset="utf-8" />
<link href="index.xhtml#Top" rel="start" title="Top" />
<link href="Term-Index.xhtml#Term-Index" rel="index" title="Term Index" />
<link href="index.xhtml#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="Chapter-2.xhtml#Chapter-2" rel="prev" title="Chapter 2" />
<link href="Chapter-3.xhtml#Chapter-3" rel="next" title="Chapter 3" />
<link href="2_002e4.xhtml#g_t2_002e4_002e3" rel="prev" title="2.4.3" />

<link href="css/style.css" rel="stylesheet" type="text/css" />
<link href="css/prettify.css" rel="stylesheet" type="text/css" />

<script src="js/jquery.min.js" type="text/javascript"></script>
<script src="js/footnotes.js" type="text/javascript"></script>
<script src="js/browsertest.js" type="text/javascript"></script>
</head>

<body>
<section><span class="top jump" title="Jump to top"><a href="#pagetop" accesskey="t">⇡</a></span><a id="pagetop"></a><a id="g_t2_002e5"></a>
<nav class="header">
<p>
Next: <a href="Chapter-3.xhtml#Chapter-3" accesskey="n" rel="next">Chapter 3</a>, Prev: <a href="2_002e4.xhtml#g_t2_002e4" accesskey="p" rel="prev">2.4</a>, Up: <a href="Chapter-2.xhtml#Chapter-2" accesskey="u" rel="prev">Chapter 2</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>
<a id="Systems-with-Generic-Operations"></a>
<h3 class="section"><span class="secnum">2.5</span><span class="sectitle">Systems with Generic Operations</span></h3>

<p>In the previous section, we saw how to design systems in which data objects can
be represented in more than one way.  The key idea is to link the code that
specifies the data operations to the several representations by means of
generic interface procedures.  Now we will see how to use this same idea not
only to define operations that are generic over different representations but
also to define operations that are generic over different kinds of arguments.
We have already seen several different packages of arithmetic operations: the
primitive arithmetic (<code>+</code>, <code>-</code>, <code>*</code>, <code>/</code>) built into our
language, the rational-number arithmetic (<code>add-rat</code>, <code>sub-rat</code>,
<code>mul-rat</code>, <code>div-rat</code>) of <a href="2_002e1.xhtml#g_t2_002e1_002e1">2.1.1</a>, and the complex-number
arithmetic that we implemented in <a href="2_002e4.xhtml#g_t2_002e4_002e3">2.4.3</a>.  We will now use
data-directed techniques to construct a package of arithmetic operations that
incorporates all the arithmetic packages we have already constructed.
</p>
<p><a href="#Figure-2_002e23">Figure 2.23</a> shows the structure of the system we shall build.  Notice the
abstraction barriers.  From the perspective of someone using “numbers,” there
is a single procedure <code>add</code> that operates on whatever numbers are
supplied.  <code>Add</code> is part of a generic interface that allows the separate
ordinary-arithmetic, rational-arithmetic, and complex-arithmetic packages to be
accessed uniformly by programs that use numbers.  Any individual arithmetic
package (such as the complex package) may itself be accessed through generic
procedures (such as <code>add-complex</code>) that combine packages designed for
different representations (such as rectangular and polar).  Moreover, the
structure of the system is additive, so that one can design the individual
arithmetic packages separately and combine them to produce a generic arithmetic
system.
</p>
<figure class="float">
<a id="Figure-2_002e23"></a>
<object style="width: 59.40ex; height: 54.22ex;" data="fig/chap2/Fig2.23b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 2.23:</strong> Generic arithmetic system.</p>
</figcaption>
</figure>


<a id="g_t2_002e5_002e1"></a>
<a id="Generic-Arithmetic-Operations"></a>
<h4 class="subsection"><span class="secnum">2.5.1</span><span class="sectitle">Generic Arithmetic Operations</span></h4>

<p>The task of designing generic arithmetic operations is analogous to that of
designing the generic complex-number operations.  We would like, for instance,
to have a generic addition procedure <code>add</code> that acts like ordinary
primitive addition <code>+</code> on ordinary numbers, like <code>add-rat</code> on
rational numbers, and like <code>add-complex</code> on complex numbers.  We can
implement <code>add</code>, and the other generic arithmetic operations, by following
the same strategy we used in <a href="2_002e4.xhtml#g_t2_002e4_002e3">2.4.3</a> to implement the generic
selectors for complex numbers.  We will attach a type tag to each kind of
number and cause the generic procedure to dispatch to an appropriate package
according to the data type of its arguments.
</p>
<p>The generic arithmetic procedures are defined as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add x y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">apply-generic </span><span class="lit">'add</span><span class="pln"> x y</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sub x y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">apply-generic </span><span class="lit">'sub</span><span class="pln"> x y</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">mul x y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">apply-generic </span><span class="lit">'mul</span><span class="pln"> x y</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">div x y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">apply-generic </span><span class="lit">'div</span><span class="pln"> x y</span><span class="clo">))</span></pre></div>

<p>We begin by installing a package for handling <a id="index-ordinary"></a>
<em>ordinary</em> numbers, that
is, the primitive numbers of our language.  We will tag these with the symbol
<code>scheme-number</code>.  The arithmetic operations in this package are the
primitive arithmetic procedures (so there is no need to define extra procedures
to handle the untagged numbers).  Since these operations each take two
arguments, they are installed in the table keyed by the list
<code>(scheme-number scheme-number)</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">install-scheme-number-package</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tag x</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">attach-tag </span><span class="lit">'scheme-number</span><span class="pln"> x</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">put </span><span class="lit">'add</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">scheme-number scheme-number</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tag </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x y</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">put </span><span class="lit">'sub</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">scheme-number scheme-number</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tag </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> x y</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">put </span><span class="lit">'mul</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">scheme-number scheme-number</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tag </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x y</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">put </span><span class="lit">'div</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">scheme-number scheme-number</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tag </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> x y</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">put </span><span class="lit">'make</span><span class="pln"> </span><span class="lit">'scheme-number</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tag x</span><span class="clo">)))</span><span class="pln">
  </span><span class="lit">'done</span><span class="clo">)</span></pre></div>

<p>Users of the Scheme-number package will create (tagged) ordinary numbers by
means of the procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-scheme-number n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">get </span><span class="lit">'make</span><span class="pln"> </span><span class="lit">'scheme-number</span><span class="clo">)</span><span class="pln"> n</span><span class="clo">))</span></pre></div>

<p>Now that the framework of the generic arithmetic system is in place, we can
readily include new kinds of numbers.  Here is a package that performs rational
arithmetic.  Notice that, as a benefit of additivity, we can use without
modification the rational-number code from <a href="2_002e1.xhtml#g_t2_002e1_002e1">2.1.1</a> as the internal
procedures in the package:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">install-rational-package</span><span class="clo">)</span><span class="pln">
  </span><span class="roman"><span class="com">;; internal procedures</span></span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">numer x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> x</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">denom x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> x</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-rat n d</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">g </span><span class="opn">(</span><span class="pln">gcd n d</span><span class="clo">)))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> n g</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> d g</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add-rat x y</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">make-rat </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">numer x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">denom y</span><span class="clo">))</span><span class="pln">
                 </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">numer y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">denom x</span><span class="clo">)))</span><span class="pln">
              </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">denom x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">denom y</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sub-rat x y</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">make-rat </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">numer x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">denom y</span><span class="clo">))</span><span class="pln">
                 </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">numer y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">denom x</span><span class="clo">)))</span><span class="pln">
              </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">denom x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">denom y</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">mul-rat x y</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">make-rat </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">numer x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">numer y</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">denom x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">denom y</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">div-rat x y</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">make-rat </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">numer x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">denom y</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">denom x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">numer y</span><span class="clo">))))</span><span class="pln">
  </span><span class="roman"><span class="com">;; interface to rest of the system</span></span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tag x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">attach-tag </span><span class="lit">'rational</span><span class="pln"> x</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">put </span><span class="lit">'add</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">rational rational</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tag </span><span class="opn">(</span><span class="pln">add-rat x y</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">put </span><span class="lit">'sub</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">rational rational</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tag </span><span class="opn">(</span><span class="pln">sub-rat x y</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">put </span><span class="lit">'mul</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">rational rational</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tag </span><span class="opn">(</span><span class="pln">mul-rat x y</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">put </span><span class="lit">'div</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">rational rational</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tag </span><span class="opn">(</span><span class="pln">div-rat x y</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">put </span><span class="lit">'make</span><span class="pln"> </span><span class="lit">'rational</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">n d</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tag </span><span class="opn">(</span><span class="pln">make-rat n d</span><span class="clo">))))</span><span class="pln">
  </span><span class="lit">'done</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-rational n d</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">get </span><span class="lit">'make</span><span class="pln"> </span><span class="lit">'rational</span><span class="clo">)</span><span class="pln"> n d</span><span class="clo">))</span></pre></div>

<p>We can install a similar package to handle complex numbers, using the tag
<code>complex</code>.  In creating the package, we extract from the table the
operations <code>make-from-real-imag</code> and <code>make-from-mag-ang</code> that were
defined by the rectangular and polar packages.  Additivity permits us to use,
as the internal operations, the same <code>add-complex</code>, <code>sub-complex</code>,
<code>mul-complex</code>, and <code>div-complex</code> procedures from <a href="2_002e4.xhtml#g_t2_002e4_002e1">2.4.1</a>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">install-complex-package</span><span class="clo">)</span><span class="pln">
  </span><span class="roman"><span class="com">;; imported procedures from rectangular</span></span><span class="com"> </span><span class="pln">
  </span><span class="roman"><span class="com">;; and polar packages</span></span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-from-real-imag x y</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">((</span><span class="pln">get </span><span class="lit">'make-from-real-imag</span><span class="pln"> 
          </span><span class="lit">'rectangular</span><span class="clo">)</span><span class="pln"> 
     x y</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-from-mag-ang r a</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">((</span><span class="pln">get </span><span class="lit">'make-from-mag-ang</span><span class="pln"> </span><span class="lit">'polar</span><span class="clo">)</span><span class="pln"> 
     r a</span><span class="clo">))</span><span class="pln">
  </span><span class="roman"><span class="com">;; internal procedures</span></span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add-complex z1 z2</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">make-from-real-imag 
     </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">real-part z1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">real-part z2</span><span class="clo">))</span><span class="pln">
     </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">imag-part z1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">imag-part z2</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sub-complex z1 z2</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">make-from-real-imag 
     </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="opn">(</span><span class="pln">real-part z1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">real-part z2</span><span class="clo">))</span><span class="pln">
     </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="opn">(</span><span class="pln">imag-part z1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">imag-part z2</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">mul-complex z1 z2</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">make-from-mag-ang 
     </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">magnitude z1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">magnitude z2</span><span class="clo">))</span><span class="pln">
     </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">angle z1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">angle z2</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">div-complex z1 z2</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">make-from-mag-ang 
     </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> </span><span class="opn">(</span><span class="pln">magnitude z1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">magnitude z2</span><span class="clo">))</span><span class="pln">
     </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="opn">(</span><span class="pln">angle z1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">angle z2</span><span class="clo">))))</span><span class="pln">
  </span><span class="roman"><span class="com">;; interface to rest of the system</span></span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tag z</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">attach-tag </span><span class="lit">'complex</span><span class="pln"> z</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">put </span><span class="lit">'add</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">complex complex</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">z1 z2</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">tag </span><span class="opn">(</span><span class="pln">add-complex z1 z2</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">put </span><span class="lit">'sub</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">complex complex</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">z1 z2</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">tag </span><span class="opn">(</span><span class="pln">sub-complex z1 z2</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">put </span><span class="lit">'mul</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">complex complex</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">z1 z2</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">tag </span><span class="opn">(</span><span class="pln">mul-complex z1 z2</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">put </span><span class="lit">'div</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">complex complex</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">z1 z2</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">tag </span><span class="opn">(</span><span class="pln">div-complex z1 z2</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">put </span><span class="lit">'make-from-real-imag</span><span class="pln"> </span><span class="lit">'complex</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">tag </span><span class="opn">(</span><span class="pln">make-from-real-imag x y</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">put </span><span class="lit">'make-from-mag-ang</span><span class="pln"> </span><span class="lit">'complex</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">r a</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">tag </span><span class="opn">(</span><span class="pln">make-from-mag-ang r a</span><span class="clo">))))</span><span class="pln">
  </span><span class="lit">'done</span><span class="clo">)</span></pre></div>

<p>Programs outside the complex-number package can construct complex numbers
either from real and imaginary parts or from magnitudes and angles.  Notice how
the underlying procedures, originally defined in the rectangular and polar
packages, are exported to the complex package, and exported from there to the
outside world.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-complex-from-real-imag x y</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">get </span><span class="lit">'make-from-real-imag</span><span class="pln"> </span><span class="lit">'complex</span><span class="clo">)</span><span class="pln"> x y</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-complex-from-mag-ang r a</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">get </span><span class="lit">'make-from-mag-ang</span><span class="pln"> </span><span class="lit">'complex</span><span class="clo">)</span><span class="pln"> r a</span><span class="clo">))</span></pre></div>

<p>What we have here is a two-level tag system.  A typical complex number, such as
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>3</mn>
    <mo>+</mo>
    <mn>4</mn>
    <mi>i</mi>
  </mrow>
</math> in rectangular form, would be represented as shown in <a href="#Figure-2_002e24">Figure 2.24</a>.  
The outer tag (<code>complex</code>) is used to direct the number to the
complex package.  Once within the complex package, the next tag
(<code>rectangular</code>) is used to direct the number to the rectangular package.
In a large and complicated system there might be many levels, each interfaced
with the next by means of generic operations.  As a data object is passed
“downward,” the outer tag that is used to direct it to the appropriate
package is stripped off (by applying <code>contents</code>) and the next level of tag
(if any) becomes visible to be used for further dispatching.
</p>
<figure class="float">
<a id="Figure-2_002e24"></a>
<object style="width: 41.53ex; height: 12.00ex;" data="fig/chap2/Fig2.24d.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 2.24:</strong> Representation of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>3</mn>
    <mo>+</mo>
    <mn>4</mn>
    <mi>i</mi>
  </mrow>
</math> in rectangular form.</p>
</figcaption>
</figure>

<p>In the above packages, we used <code>add-rat</code>, <code>add-complex</code>, and the
other arithmetic procedures exactly as originally written.  Once these
definitions are internal to different installation procedures, however, they no
longer need names that are distinct from each other: we could simply name them
<code>add</code>, <code>sub</code>, <code>mul</code>, and <code>div</code> in both packages.
</p>
<blockquote>
<p><strong><a id="Exercise-2_002e77"></a>Exercise 2.77:</strong> Louis Reasoner tries to evaluate
the expression <code>(magnitude z)</code> where <code>z</code> is the object shown in
<a href="#Figure-2_002e24">Figure 2.24</a>.  To his surprise, instead of the answer 5 he gets an error
message from <code>apply-generic</code>, saying there is no method for the operation
<code>magnitude</code> on the types <code>(complex)</code>.  He shows this interaction to
Alyssa P. Hacker, who says “The problem is that the complex-number selectors
were never defined for <code>complex</code> numbers, just for <code>polar</code> and
<code>rectangular</code> numbers.  All you have to do to make this work is add the
following to the <code>complex</code> package:”
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">put </span><span class="lit">'real-part</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">complex</span><span class="clo">)</span><span class="pln"> real-part</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">put </span><span class="lit">'imag-part</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">complex</span><span class="clo">)</span><span class="pln"> imag-part</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">put </span><span class="lit">'magnitude</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">complex</span><span class="clo">)</span><span class="pln"> magnitude</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">put </span><span class="lit">'angle</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">complex</span><span class="clo">)</span><span class="pln"> angle</span><span class="clo">)</span></pre></div>

<p>Describe in detail why this works.  As an example, trace through all the
procedures called in evaluating the expression <code>(magnitude z)</code> where
<code>z</code> is the object shown in <a href="#Figure-2_002e24">Figure 2.24</a>.  In particular, how many
times is <code>apply-generic</code> invoked?  What procedure is dispatched to in each
case?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e78"></a>Exercise 2.78:</strong> The internal procedures in the
<code>scheme-number</code> package are essentially nothing more than calls to the
primitive procedures <code>+</code>, <code>-</code>, etc.  It was not possible to use the
primitives of the language directly because our type-tag system requires that
each data object have a type attached to it.  In fact, however, all Lisp
implementations do have a type system, which they use internally.  Primitive
predicates such as <code>symbol?</code> and <code>number?</code>  determine whether data
objects have particular types.  Modify the definitions of <code>type-tag</code>,
<code>contents</code>, and <code>attach-tag</code> from <a href="2_002e4.xhtml#g_t2_002e4_002e2">2.4.2</a> so that our
generic system takes advantage of Scheme’s internal type system.  That is to
say, the system should work as before except that ordinary numbers should be
represented simply as Scheme numbers rather than as pairs whose <code>car</code> is
the symbol <code>scheme-number</code>.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e79"></a>Exercise 2.79:</strong> Define a generic equality
predicate <code>equ?</code> that tests the equality of two numbers, and install it in
the generic arithmetic package.  This operation should work for ordinary
numbers, rational numbers, and complex numbers.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e80"></a>Exercise 2.80:</strong> Define a generic predicate
<code>=zero?</code> that tests if its argument is zero, and install it in the generic
arithmetic package.  This operation should work for ordinary numbers, rational
numbers, and complex numbers.
</p></blockquote>

<a id="g_t2_002e5_002e2"></a>
<a id="Combining-Data-of-Different-Types"></a>
<h4 class="subsection"><span class="secnum">2.5.2</span><span class="sectitle">Combining Data of Different Types</span></h4>

<p>We have seen how to define a unified arithmetic system that encompasses
ordinary numbers, complex numbers, rational numbers, and any other type of
number we might decide to invent, but we have ignored an important issue.  The
operations we have defined so far treat the different data types as being
completely independent.  Thus, there are separate packages for adding, say, two
ordinary numbers, or two complex numbers.  What we have not yet considered is
the fact that it is meaningful to define operations that cross the type
boundaries, such as the addition of a complex number to an ordinary number.  We
have gone to great pains to introduce barriers between parts of our programs so
that they can be developed and understood separately.  We would like to
introduce the cross-type operations in some carefully controlled way, so that
we can support them without seriously violating our module boundaries.
</p>
<p>One way to handle cross-type operations is to design a different procedure for
each possible combination of types for which the operation is valid.  For
example, we could extend the complex-number package so that it provides a
procedure for adding complex numbers to ordinary numbers and installs this in
the table using the tag <code>(complex scheme-number)</code>:<a class="footnote_link" id="DOCF115" href="#FOOT115"><sup>115</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add-complex-to-schemenum z x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">make-from-real-imag </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">real-part z</span><span class="clo">)</span><span class="pln"> x</span><span class="clo">)</span><span class="pln">
                       </span><span class="opn">(</span><span class="pln">imag-part z</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">put </span><span class="lit">'add</span><span class="pln"> 
     </span><span class="lit">'</span><span class="opn">(</span><span class="pln">complex scheme-number</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">z x</span><span class="clo">)</span><span class="pln"> 
       </span><span class="opn">(</span><span class="pln">tag </span><span class="opn">(</span><span class="pln">add-complex-to-schemenum z x</span><span class="clo">))))</span></pre></div>

<p>This technique works, but it is cumbersome.  With such a system, the cost of
introducing a new type is not just the construction of the package of
procedures for that type but also the construction and installation of the
procedures that implement the cross-type operations.  This can easily be much
more code than is needed to define the operations on the type itself.  The
method also undermines our ability to combine separate packages additively, or
at least to limit the extent to which the implementors of the individual packages
need to take account of other packages.  For instance, in the example above, it
seems reasonable that handling mixed operations on complex numbers and ordinary
numbers should be the responsibility of the complex-number package.  Combining
rational numbers and complex numbers, however, might be done by the complex
package, by the rational package, or by some third package that uses operations
extracted from these two packages.  Formulating coherent policies on the
division of responsibility among packages can be an overwhelming task in
designing systems with many packages and many cross-type operations.
</p>
<a id="Coercion"></a>
<h5 class="subsubheading">Coercion</h5>

<p>In the general situation of completely unrelated operations acting on
completely unrelated types, implementing explicit cross-type operations,
cumbersome though it may be, is the best that one can hope for.  Fortunately,
we can usually do better by taking advantage of additional structure that may
be latent in our type system.  Often the different data types are not
completely independent, and there may be ways by which objects of one type may
be viewed as being of another type.  This process is called <a id="index-coercion"></a>
<em>coercion</em>.
For example, if we are asked to arithmetically combine an ordinary number with
a complex number, we can view the ordinary number as a complex number whose
imaginary part is zero.  This transforms the problem to that of combining two
complex numbers, which can be handled in the ordinary way by the
complex-arithmetic package.
</p>
<p>In general, we can implement this idea by designing coercion procedures that
transform an object of one type into an equivalent object of another type.
Here is a typical coercion procedure, which transforms a given ordinary number
to a complex number with that real part and zero imaginary part:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">scheme-number-</span><span class="pun">&gt;</span><span class="pln">complex n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">make-complex-from-real-imag 
   </span><span class="opn">(</span><span class="pln">contents n</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0</span><span class="clo">))</span></pre></div>

<p>We install these coercion procedures in a special coercion table, indexed under
the names of the two types:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">put-coercion </span><span class="lit">'scheme-number</span><span class="pln"> </span><span class="lit">'complex</span><span class="pln"> 
              scheme-number-</span><span class="pun">&gt;</span><span class="pln">complex</span><span class="clo">)</span></pre></div>

<p>(We assume that there are <code>put-coercion</code> and <code>get-coercion</code>
procedures available for manipulating this table.)  Generally some of the slots
in the table will be empty, because it is not generally possible to coerce an
arbitrary data object of each type into all other types.  For example, there is
no way to coerce an arbitrary complex number to an ordinary number, so there
will be no general <code>complex-&gt;scheme-number</code> procedure included in the
table.
</p>
<p>Once the coercion table has been set up, we can handle coercion in a uniform
manner by modifying the <code>apply-generic</code> procedure of <a href="2_002e4.xhtml#g_t2_002e4_002e3">2.4.3</a>.
When asked to apply an operation, we first check whether the operation is
defined for the arguments’ types, just as before.  If so, we dispatch to the
procedure found in the operation-and-type table.  Otherwise, we try coercion.
For simplicity, we consider only the case where there are two
arguments.<a class="footnote_link" id="DOCF116" href="#FOOT116"><sup>116</sup></a>  We check the
coercion table to see if objects of the first type can be coerced to the second
type.  If so, we coerce the first argument and try the operation again.  If
objects of the first type cannot in general be coerced to the second type, we
try the coercion the other way around to see if there is a way to coerce the
second argument to the type of the first argument.  Finally, if there is no
known way to coerce either type to the other type, we give up.  Here is the
procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">apply-generic op </span><span class="pun">.</span><span class="pln"> args</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">type-tags </span><span class="opn">(</span><span class="pln">map type-tag args</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">proc </span><span class="opn">(</span><span class="pln">get op type-tags</span><span class="clo">)))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> proc
          </span><span class="opn">(</span><span class="pln">apply proc </span><span class="opn">(</span><span class="pln">map contents args</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> </span><span class="opn">(</span><span class="pln">length args</span><span class="clo">)</span><span class="pln"> </span><span class="lit">2</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">type1 </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> type-tags</span><span class="clo">))</span><span class="pln">
                    </span><span class="opn">(</span><span class="pln">type2 </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> type-tags</span><span class="clo">))</span><span class="pln">
                    </span><span class="opn">(</span><span class="pln">a1 </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> args</span><span class="clo">))</span><span class="pln">
                    </span><span class="opn">(</span><span class="pln">a2 </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> args</span><span class="clo">)))</span><span class="pln">
                </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">t1-</span><span class="pun">&gt;</span><span class="pln">t2 
                       </span><span class="opn">(</span><span class="pln">get-coercion type1
                                     type2</span><span class="clo">))</span><span class="pln">
                      </span><span class="opn">(</span><span class="pln">t2-</span><span class="pun">&gt;</span><span class="pln">t1 
                       </span><span class="opn">(</span><span class="pln">get-coercion type2 
                                     type1</span><span class="clo">)))</span><span class="pln">
                  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">(</span><span class="pln">t1-</span><span class="pun">&gt;</span><span class="pln">t2
                         </span><span class="opn">(</span><span class="pln">apply-generic 
                          op </span><span class="opn">(</span><span class="pln">t1-</span><span class="pun">&gt;</span><span class="pln">t2 a1</span><span class="clo">)</span><span class="pln"> a2</span><span class="clo">))</span><span class="pln">
                        </span><span class="opn">(</span><span class="pln">t2-</span><span class="pun">&gt;</span><span class="pln">t1
                         </span><span class="opn">(</span><span class="pln">apply-generic 
                          op a1 </span><span class="opn">(</span><span class="pln">t2-</span><span class="pun">&gt;</span><span class="pln">t1 a2</span><span class="clo">)))</span><span class="pln">
                        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
                         </span><span class="opn">(</span><span class="err">error</span><span class="pln"> 
                          </span><span class="str">"No method for 
                           these types"</span><span class="pln">
                          </span><span class="opn">(</span><span class="pln">list 
                           op 
                           type-tags</span><span class="clo">))))))</span><span class="pln">
              </span><span class="opn">(</span><span class="err">error</span><span class="pln"> 
               </span><span class="str">"No method for these types"</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">list op type-tags</span><span class="clo">)))))))</span></pre></div>

<p>This coercion scheme has many advantages over the method of defining explicit
cross-type operations, as outlined above.  Although we still need to write
coercion procedures to relate the types (possibly <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mn>2</mn>
  </msup>
</math> procedures for a
system with <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> types), we need to write only one procedure for each pair of
types rather than a different procedure for each collection of types and each
generic operation.<a class="footnote_link" id="DOCF117" href="#FOOT117"><sup>117</sup></a>  What we are counting on here is the fact
that the appropriate transformation between types depends only on the types
themselves, not on the operation to be applied.
</p>
<p>On the other hand, there may be applications for which our coercion scheme is
not general enough.  Even when neither of the objects to be combined can be
converted to the type of the other it may still be possible to perform the
operation by converting both objects to a third type.  In order to deal with
such complexity and still preserve modularity in our programs, it is usually
necessary to build systems that take advantage of still further structure in
the relations among types, as we discuss next.
</p>
<a id="Hierarchies-of-types"></a>
<h5 class="subsubheading">Hierarchies of types</h5>

<p>The coercion scheme presented above relied on the existence of natural
relations between pairs of types.  Often there is more “global” structure in
how the different types relate to each other.  For instance, suppose we are
building a generic arithmetic system to handle integers, rational numbers, real
numbers, and complex numbers.  In such a system, it is quite natural to regard
an integer as a special kind of rational number, which is in turn a special
kind of real number, which is in turn a special kind of complex number.  What
we actually have is a so-called <a id="index-hierarchy-of-types"></a>
<em>hierarchy of types</em>, in which, for
example, integers are a <a id="index-subtype"></a>
<em>subtype</em> of rational numbers (i.e., any
operation that can be applied to a rational number can automatically be applied
to an integer).  Conversely, we say that rational numbers form a
<a id="index-supertype"></a>
<em>supertype</em> of integers.  The particular hierarchy we have here is of a
very simple kind, in which each type has at most one supertype and at most one
subtype.  Such a structure, called a <a id="index-tower"></a>
<em>tower</em>, is illustrated in
<a href="#Figure-2_002e25">Figure 2.25</a>.
</p>
<figure class="float">
<a id="Figure-2_002e25"></a>
<object style="width: 8.46ex; height: 22.71ex;" data="fig/chap2/Fig2.25.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 2.25:</strong> A tower of types.</p>
</figcaption>
</figure>

<p>If we have a tower structure, then we can greatly simplify the problem of
adding a new type to the hierarchy, for we need only specify how the new type
is embedded in the next supertype above it and how it is the supertype of the
type below it.  For example, if we want to add an integer to a complex number,
we need not explicitly define a special coercion procedure
<code>integer-&gt;complex</code>.  Instead, we define how an integer can be transformed
into a rational number, how a rational number is transformed into a real
number, and how a real number is transformed into a complex number.  We then
allow the system to transform the integer into a complex number through these
steps and then add the two complex numbers.
</p>
<p>We can redesign our <code>apply-generic</code> procedure in the following way: For
each type, we need to supply a <code>raise</code> procedure, which “raises” objects
of that type one level in the tower.  Then when the system is required to
operate on objects of different types it can successively raise the lower types
until all the objects are at the same level in the tower.  (<a href="#Exercise-2_002e83">Exercise 2.83</a>
and <a href="#Exercise-2_002e84">Exercise 2.84</a> concern the details of implementing such a strategy.)
</p>
<p>Another advantage of a tower is that we can easily implement the notion that
every type “inherits” all operations defined on a supertype.  For instance,
if we do not supply a special procedure for finding the real part of an
integer, we should nevertheless expect that <code>real-part</code> will be defined
for integers by virtue of the fact that integers are a subtype of complex
numbers.  In a tower, we can arrange for this to happen in a uniform way by
modifying <code>apply-generic</code>.  If the required operation is not directly
defined for the type of the object given, we raise the object to its supertype
and try again.  We thus crawl up the tower, transforming our argument as we go,
until we either find a level at which the desired operation can be performed or
hit the top (in which case we give up).
</p>
<p>Yet another advantage of a tower over a more general hierarchy is that it gives
us a simple way to “lower” a data object to the simplest representation.  For
example, if we add <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>2</mn>
    <mo>+</mo>
    <mn>3</mn>
    <mi>i</mi>
  </mrow>
</math> to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>4</mn>
    <mo>−<!-- − --></mo>
    <mn>3</mn>
    <mi>i</mi>
  </mrow>
</math>, it would be nice to obtain the
answer as the integer 6 rather than as the complex number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>6</mn>
    <mo>+</mo>
    <mn>0</mn>
    <mi>i</mi>
  </mrow>
</math>.
<a href="#Exercise-2_002e85">Exercise 2.85</a> discusses a way to implement such a lowering operation.
(The trick is that we need a general way to distinguish those objects that can
be lowered, such as <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>6</mn>
    <mo>+</mo>
    <mn>0</mn>
    <mi>i</mi>
  </mrow>
</math>, from those that cannot, such as <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>6</mn>
    <mo>+</mo>
    <mn>2</mn>
    <mi>i</mi>
  </mrow>
</math>.)
</p>
<a id="Inadequacies-of-hierarchies"></a>
<h5 class="subsubheading">Inadequacies of hierarchies</h5>

<p>If the data types in our system can be naturally arranged in a tower, this
greatly simplifies the problems of dealing with generic operations on different
types, as we have seen.  Unfortunately, this is usually not the case.
<a href="#Figure-2_002e26">Figure 2.26</a> illustrates a more complex arrangement of mixed types, this
one showing relations among different types of geometric figures.  We see that,
in general, a type may have more than one subtype.  Triangles and
quadrilaterals, for instance, are both subtypes of polygons.  In addition, a
type may have more than one supertype.  For example, an isosceles right
triangle may be regarded either as an isosceles triangle or as a right
triangle.  This multiple-supertypes issue is particularly thorny, since it
means that there is no unique way to “raise” a type in the hierarchy.
Finding the “correct” supertype in which to apply an operation to an object
may involve considerable searching through the entire type network on the part
of a procedure such as <code>apply-generic</code>.  Since there generally are
multiple subtypes for a type, there is a similar problem in coercing a value
“down” the type hierarchy.  Dealing with large numbers of interrelated types
while still preserving modularity in the design of large systems is very
difficult, and is an area of much current research.<a class="footnote_link" id="DOCF118" href="#FOOT118"><sup>118</sup></a>
</p>
<figure class="float">
<a id="Figure-2_002e26"></a>
<object style="width: 68.12ex; height: 44.21ex;" data="fig/chap2/Fig2.26f.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 2.26:</strong> Relations among types of geometric figures.</p>
</figcaption>
</figure>

<blockquote>
<p><strong><a id="Exercise-2_002e81"></a>Exercise 2.81:</strong> Louis Reasoner has noticed that
<code>apply-generic</code> may try to coerce the arguments to each other’s type even
if they already have the same type.  Therefore, he reasons, we need to put
procedures in the coercion table to <a id="index-coerce"></a>
<em>coerce</em> arguments of each type to
their own type.  For example, in addition to the
<code>scheme-number-&gt;complex</code> coercion shown above, he would do:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">scheme-number-</span><span class="pun">&gt;</span><span class="pln">scheme-number n</span><span class="clo">)</span><span class="pln"> n</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">complex-</span><span class="pun">&gt;</span><span class="pln">complex z</span><span class="clo">)</span><span class="pln"> z</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="pln">put-coercion </span><span class="lit">'scheme-number</span><span class="pln"> </span><span class="lit">'scheme-number</span><span class="pln">
              scheme-number-</span><span class="pun">&gt;</span><span class="pln">scheme-number</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="pln">put-coercion </span><span class="lit">'complex</span><span class="pln"> </span><span class="lit">'complex</span><span class="pln"> 
              complex-</span><span class="pun">&gt;</span><span class="pln">complex</span><span class="clo">)</span></pre></div>

<ol>
<li> With Louis’s coercion procedures installed, what happens if
<code>apply-generic</code> is called with two arguments of type <code>scheme-number</code>
or two arguments of type <code>complex</code> for an operation that is not found in
the table for those types?  For example, assume that we’ve defined a generic
exponentiation operation:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">exp x y</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">apply-generic </span><span class="lit">'exp</span><span class="pln"> x y</span><span class="clo">))</span></pre></div>

<p>and have put a procedure for exponentiation in the Scheme-number
package but not in any other package:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="roman"><span class="com">;; following added to Scheme-number package</span></span><span class="pln">
</span><span class="opn">(</span><span class="pln">put </span><span class="lit">'exp</span><span class="pln"> 
     </span><span class="lit">'</span><span class="opn">(</span><span class="pln">scheme-number scheme-number</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y</span><span class="clo">)</span><span class="pln"> 
       </span><span class="opn">(</span><span class="pln">tag </span><span class="opn">(</span><span class="pln">expt x y</span><span class="clo">))))</span><span class="pln"> 
       </span><span class="roman"><span class="com">; using primitive </span><code><span class="com">expt</span></code></span>
</pre></div>

<p>What happens if we call <code>exp</code> with two complex numbers as arguments?
</p>
</li><li> Is Louis correct that something had to be done about coercion with arguments of
the same type, or does <code>apply-generic</code> work correctly as is?

</li><li> Modify <code>apply-generic</code> so that it doesn’t try coercion if the two
arguments have the same type.

</li></ol>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e82"></a>Exercise 2.82:</strong> Show how to generalize
<code>apply-generic</code> to handle coercion in the general case of multiple
arguments.  One strategy is to attempt to coerce all the arguments to the type
of the first argument, then to the type of the second argument, and so on.
Give an example of a situation where this strategy (and likewise the
two-argument version given above) is not sufficiently general.  (Hint: Consider
the case where there are some suitable mixed-type operations present in the
table that will not be tried.)
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e83"></a>Exercise 2.83:</strong> Suppose you are designing a
generic arithmetic system for dealing with the tower of types shown in
<a href="#Figure-2_002e25">Figure 2.25</a>: integer, rational, real, complex.  For each type (except
complex), design a procedure that raises objects of that type one level in the
tower.  Show how to install a generic <code>raise</code> operation that will work for
each type (except complex).
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e84"></a>Exercise 2.84:</strong> Using the <code>raise</code> operation
of <a href="#Exercise-2_002e83">Exercise 2.83</a>, modify the <code>apply-generic</code> procedure so that it
coerces its arguments to have the same type by the method of successive
raising, as discussed in this section.  You will need to devise a way to test
which of two types is higher in the tower.  Do this in a manner that is
“compatible” with the rest of the system and will not lead to problems in
adding new levels to the tower.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e85"></a>Exercise 2.85:</strong> This section mentioned a method
for “simplifying” a data object by lowering it in the tower of types as far
as possible.  Design a procedure <code>drop</code> that accomplishes this for the
tower described in <a href="#Exercise-2_002e83">Exercise 2.83</a>.  The key is to decide, in some general
way, whether an object can be lowered.  For example, the complex number 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>1.5</mn>
    <mo>+</mo>
    <mn>0</mn>
    <mi>i</mi>
  </mrow>
</math> can be lowered as far as <code>real</code>, the complex number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>1</mn>
    <mo>+</mo>
    <mn>0</mn>
    <mi>i</mi>
  </mrow>
</math> can
be lowered as far as <code>integer</code>, and the complex number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>2</mn>
    <mo>+</mo>
    <mn>3</mn>
    <mi>i</mi>
  </mrow>
</math> cannot
be lowered at all.  Here is a plan for determining whether an object can be
lowered: Begin by defining a generic operation <code>project</code> that “pushes”
an object down in the tower.  For example, projecting a complex number would
involve throwing away the imaginary part.  Then a number can be dropped if,
when we <code>project</code> it and <code>raise</code> the result back to the type we
started with, we end up with something equal to what we started with.  Show how
to implement this idea in detail, by writing a <code>drop</code> procedure that drops
an object as far as possible.  You will need to design the various projection
operations<a class="footnote_link" id="DOCF119" href="#FOOT119"><sup>119</sup></a> and
install <code>project</code> as a generic operation in the system.  You will also
need to make use of a generic equality predicate, such as described in
<a href="#Exercise-2_002e79">Exercise 2.79</a>.  Finally, use <code>drop</code> to rewrite <code>apply-generic</code>
from <a href="#Exercise-2_002e84">Exercise 2.84</a> so that it “simplifies” its answers.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e86"></a>Exercise 2.86:</strong> Suppose we want to handle complex
numbers whose real parts, imaginary parts, magnitudes, and angles can be either
ordinary numbers, rational numbers, or other numbers we might wish to add to
the system.  Describe and implement the changes to the system needed to
accommodate this.  You will have to define operations such as <code>sine</code> and
<code>cosine</code> that are generic over ordinary numbers and rational numbers.
</p></blockquote>

<a id="g_t2_002e5_002e3"></a>
<a id="Example_003a-Symbolic-Algebra"></a>
<h4 class="subsection"><span class="secnum">2.5.3</span><span class="sectitle">Example: Symbolic Algebra</span></h4>

<p>The manipulation of symbolic algebraic expressions is a complex process that
illustrates many of the hardest problems that occur in the design of
large-scale systems.  An algebraic expression, in general, can be viewed as a
hierarchical structure, a tree of operators applied to operands.  We can
construct algebraic expressions by starting with a set of primitive objects,
such as constants and variables, and combining these by means of algebraic
operators, such as addition and multiplication.  As in other languages, we form
abstractions that enable us to refer to compound objects in simple terms.
Typical abstractions in symbolic algebra are ideas such as linear combination,
polynomial, rational function, or trigonometric function.  We can regard these
as compound “types,” which are often useful for directing the processing of
expressions.  For example, we could describe the expression
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>x</mi>
      <mn>2</mn>
    </msup>
    <mi>sin</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mo stretchy="false">(</mo>
    <msup>
      <mi>y</mi>
      <mn>2</mn>
    </msup>
    <mo>+</mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mi>cos</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mn>2</mn>
    <mi>y</mi>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>cos</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mo stretchy="false">(</mo>
    <msup>
      <mi>y</mi>
      <mn>3</mn>
    </msup>
    <mo>−<!-- − --></mo>
    <mn>2</mn>
    <msup>
      <mi>y</mi>
      <mn>2</mn>
    </msup>
    <mo stretchy="false">)</mo>
  </mrow>
</math>
as a polynomial in <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> with coefficients that are trigonometric functions of
polynomials in <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math> whose coefficients are integers.
</p>
<p>We will not attempt to develop a complete algebraic-manipulation system here.
Such systems are exceedingly complex programs, embodying deep algebraic
knowledge and elegant algorithms.  What we will do is look at a simple but
important part of algebraic manipulation: the arithmetic of polynomials.  We
will illustrate the kinds of decisions the designer of such a system faces, and
how to apply the ideas of abstract data and generic operations to help organize
this effort.
</p>
<a id="Arithmetic-on-polynomials"></a>
<h5 class="subsubheading">Arithmetic on polynomials</h5>

<p>Our first task in designing a system for performing arithmetic on polynomials
is to decide just what a polynomial is.  Polynomials are normally defined
relative to certain variables (the <a id="index-indeterminates"></a>
<em>indeterminates</em> of the polynomial).
For simplicity, we will restrict ourselves to polynomials having just one
indeterminate (<a id="index-univariate-polynomials"></a>
<em>univariate polynomials</em>).<a class="footnote_link" id="DOCF120" href="#FOOT120"><sup>120</sup></a> We will define a polynomial to be a sum of terms, each of
which is either a coefficient, a power of the indeterminate, or a product of a
coefficient and a power of the indeterminate.  A coefficient is defined as an
algebraic expression that is not dependent upon the indeterminate of the
polynomial.  For example,
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>5</mn>
    <msup>
      <mi>x</mi>
      <mn>2</mn>
    </msup>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>3</mn>
    <mi>x</mi>
  </mrow>
  <mo>+</mo>
  <mn>7</mn>
</math>
is a simple polynomial in <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math>, and
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <msup>
      <mi>y</mi>
      <mn>2</mn>
    </msup>
    <mo>+</mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
    <msup>
      <mi>x</mi>
      <mn>3</mn>
    </msup>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mn>2</mn>
    <mi>y</mi>
    <mo stretchy="false">)</mo>
    <mi>x</mi>
    <mo>+</mo>
    <mn>1</mn>
  </mrow>
</math>
is a polynomial in <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> whose coefficients are polynomials in <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math>.
</p>
<p>Already we are skirting some thorny issues.  Is the first of these polynomials
the same as the polynomial <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>5</mn>
    <msup>
      <mi>y</mi>
      <mn>2</mn>
    </msup>
    <mo>+</mo>
    <mn>3</mn>
    <mi>y</mi>
    <mo>+</mo>
    <mn>7</mn>
  </mrow>
</math>, or not?  A reasonable answer
might be “yes, if we are considering a polynomial purely as a mathematical
function, but no, if we are considering a polynomial to be a syntactic form.”
The second polynomial is algebraically equivalent to a polynomial in <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math>
whose coefficients are polynomials in <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math>.  Should our system recognize this,
or not?  Furthermore, there are other ways to represent a polynomial—for
example, as a product of factors, or (for a univariate polynomial) as the set
of roots, or as a listing of the values of the polynomial at a specified set of
points.<a class="footnote_link" id="DOCF121" href="#FOOT121"><sup>121</sup></a>  We can finesse these questions by
deciding that in our algebraic-manipulation system a “polynomial” will be a
particular syntactic form, not its underlying mathematical meaning.
</p>
<p>Now we must consider how to go about doing arithmetic on polynomials.  In this
simple system, we will consider only addition and multiplication.  Moreover, we
will insist that two polynomials to be combined must have the same
indeterminate.
</p>
<p>We will approach the design of our system by following the familiar discipline
of data abstraction.  We will represent polynomials using a data structure
called a <a id="index-poly"></a>
<em>poly</em>, which consists of a variable and a collection of
terms.  We assume that we have selectors <code>variable</code> and <code>term-list</code>
that extract those parts from a poly and a constructor <code>make-poly</code> that
assembles a poly from a given variable and a term list.  A variable will be
just a symbol, so we can use the <code>same-variable?</code>  procedure of 
<a href="2_002e3.xhtml#g_t2_002e3_002e2">2.3.2</a> to compare variables.  The following procedures define addition and
multiplication of polys:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add-poly p1 p2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">same-variable? </span><span class="opn">(</span><span class="pln">variable p1</span><span class="clo">)</span><span class="pln"> 
                      </span><span class="opn">(</span><span class="pln">variable p2</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">make-poly 
       </span><span class="opn">(</span><span class="pln">variable p1</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">add-terms </span><span class="opn">(</span><span class="pln">term-list p1</span><span class="clo">)</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">term-list p2</span><span class="clo">)))</span><span class="pln">
      </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Polys not in same var: 
              ADD-POLY"</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">list p1 p2</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">mul-poly p1 p2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">same-variable? </span><span class="opn">(</span><span class="pln">variable p1</span><span class="clo">)</span><span class="pln"> 
                      </span><span class="opn">(</span><span class="pln">variable p2</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">make-poly 
       </span><span class="opn">(</span><span class="pln">variable p1</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">mul-terms </span><span class="opn">(</span><span class="pln">term-list p1</span><span class="clo">)</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">term-list p2</span><span class="clo">)))</span><span class="pln">
      </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Polys not in same var: 
              MUL-POLY"</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">list p1 p2</span><span class="clo">))))</span></pre></div>

<p>To incorporate polynomials into our generic arithmetic system, we need to
supply them with type tags.  We’ll use the tag <code>polynomial</code>, and install
appropriate operations on tagged polynomials in the operation table.  We’ll
embed all our code in an installation procedure for the polynomial package,
similar to the ones in <a href="#g_t2_002e5_002e1">2.5.1</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">install-polynomial-package</span><span class="clo">)</span><span class="pln">
  </span><span class="roman"><span class="com">;; internal procedures</span></span><span class="pln">
  </span><span class="roman"><span class="com">;; representation of poly</span></span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-poly variable term-list</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> variable term-list</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">variable p</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> p</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">term-list p</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> p</span><span class="clo">))</span><span class="pln">
  ⟨</span><em><span class="pln">procedures </span><code><span class="pln">same-variable?</span></code><span class="pln"> 
   </span><span class="kwd">and</span><span class="pln"> </span><code><span class="pln">variable?</span></code><span class="pln"> from section </span><span class="lit">2.3.2</span></em><span class="pln">⟩

  </span><span class="roman"><span class="com">;; representation of terms and term lists</span></span><span class="pln">
  ⟨</span><em><span class="pln">procedures </span><code><span class="pln">adjoin-term</span></code><span class="pln"> </span><span class="roman"><span class="pun">…</span></span><span class="pln"> </span><code><span class="pln">coeff</span></code><span class="pln"> 
  from text below</span></em><span class="pln">⟩

  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add-poly p1 p2</span><span class="clo">)</span><span class="pln"> </span><span class="roman"><span class="pun">…</span></span><span class="clo">)</span><span class="pln">
  ⟨</span><em><span class="pln">procedures used by </span><code><span class="pln">add-poly</span></code></em><span class="pln">⟩
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">mul-poly p1 p2</span><span class="clo">)</span><span class="pln"> </span><span class="roman"><span class="pun">…</span></span><span class="clo">)</span><span class="pln">
  ⟨</span><em><span class="pln">procedures used by </span><code><span class="pln">mul-poly</span></code></em><span class="pln">⟩

  </span><span class="roman"><span class="com">;; interface to rest of the system</span></span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">tag p</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">attach-tag </span><span class="lit">'polynomial</span><span class="pln"> p</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">put </span><span class="lit">'add</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">polynomial polynomial</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">p1 p2</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">tag </span><span class="opn">(</span><span class="pln">add-poly p1 p2</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">put </span><span class="lit">'mul</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="pln">polynomial polynomial</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">p1 p2</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">tag </span><span class="opn">(</span><span class="pln">mul-poly p1 p2</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">put </span><span class="lit">'make</span><span class="pln"> </span><span class="lit">'polynomial</span><span class="pln">
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">var terms</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">tag </span><span class="opn">(</span><span class="pln">make-poly var terms</span><span class="clo">))))</span><span class="pln">
  </span><span class="lit">'done</span><span class="clo">)</span></pre></div>

<p>Polynomial addition is performed termwise.  Terms of the same order (i.e., with
the same power of the indeterminate) must be combined.  This is done by forming
a new term of the same order whose coefficient is the sum of the coefficients
of the addends.  Terms in one addend for which there are no terms of the same
order in the other addend are simply accumulated into the sum polynomial being
constructed.
</p>
<p>In order to manipulate term lists, we will assume that we have a constructor
<code>the-empty-termlist</code> that returns an empty term list and a constructor
<code>adjoin-term</code> that adjoins a new term to a term list.  We will also assume
that we have a predicate <code>empty-termlist?</code> that tells if a given term list
is empty, a selector <code>first-term</code> that extracts the highest-order term
from a term list, and a selector <code>rest-terms</code> that returns all but the
highest-order term.  To manipulate terms, we will suppose that we have a
constructor <code>make-term</code> that constructs a term with given order and
coefficient, and selectors <code>order</code> and <code>coeff</code> that return,
respectively, the order and the coefficient of the term.  These operations
allow us to consider both terms and term lists as data abstractions, whose
concrete representations we can worry about separately.
</p>
<p>Here is the procedure that constructs the term list for the sum of two
polynomials:<a class="footnote_link" id="DOCF122" href="#FOOT122"><sup>122</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add-terms L1 L2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">empty-termlist? L1</span><span class="clo">)</span><span class="pln"> L2</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">empty-termlist? L2</span><span class="clo">)</span><span class="pln"> L1</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
         </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">t1 </span><span class="opn">(</span><span class="pln">first-term L1</span><span class="clo">))</span><span class="pln"> 
               </span><span class="opn">(</span><span class="pln">t2 </span><span class="opn">(</span><span class="pln">first-term L2</span><span class="clo">)))</span><span class="pln">
           </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">&gt;</span><span class="pln"> </span><span class="opn">(</span><span class="pln">order t1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">order t2</span><span class="clo">))</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">adjoin-term
                   t1 
                   </span><span class="opn">(</span><span class="pln">add-terms </span><span class="opn">(</span><span class="pln">rest-terms L1</span><span class="clo">)</span><span class="pln"> 
                              L2</span><span class="clo">)))</span><span class="pln">
                 </span><span class="opn">((</span><span class="pun">&lt;</span><span class="pln"> </span><span class="opn">(</span><span class="pln">order t1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">order t2</span><span class="clo">))</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">adjoin-term
                   t2 
                   </span><span class="opn">(</span><span class="pln">add-terms 
                    L1 
                    </span><span class="opn">(</span><span class="pln">rest-terms L2</span><span class="clo">))))</span><span class="pln">
                 </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">adjoin-term
                   </span><span class="opn">(</span><span class="pln">make-term 
                    </span><span class="opn">(</span><span class="pln">order t1</span><span class="clo">)</span><span class="pln">
                    </span><span class="opn">(</span><span class="pln">add </span><span class="opn">(</span><span class="pln">coeff t1</span><span class="clo">)</span><span class="pln"> 
                         </span><span class="opn">(</span><span class="pln">coeff t2</span><span class="clo">)))</span><span class="pln">
                   </span><span class="opn">(</span><span class="pln">add-terms 
                    </span><span class="opn">(</span><span class="pln">rest-terms L1</span><span class="clo">)</span><span class="pln">
                    </span><span class="opn">(</span><span class="pln">rest-terms L2</span><span class="clo">)))))))))</span></pre></div>

<p>The most important point to note here is that we used the generic addition
procedure <code>add</code> to add together the coefficients of the terms being
combined.  This has powerful consequences, as we will see below.
</p>
<p>In order to multiply two term lists, we multiply each term of the first list by
all the terms of the other list, repeatedly using <code>mul-term-by-all-terms</code>,
which multiplies a given term by all terms in a given term list.  The resulting
term lists (one for each term of the first list) are accumulated into a sum.
Multiplying two terms forms a term whose order is the sum of the orders of the
factors and whose coefficient is the product of the coefficients of the
factors:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">mul-terms L1 L2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">empty-termlist? L1</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">the-empty-termlist</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">add-terms 
       </span><span class="opn">(</span><span class="pln">mul-term-by-all-terms 
        </span><span class="opn">(</span><span class="pln">first-term L1</span><span class="clo">)</span><span class="pln"> L2</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">mul-terms </span><span class="opn">(</span><span class="pln">rest-terms L1</span><span class="clo">)</span><span class="pln"> L2</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">mul-term-by-all-terms t1 L</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">empty-termlist? L</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">the-empty-termlist</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">t2 </span><span class="opn">(</span><span class="pln">first-term L</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">adjoin-term
         </span><span class="opn">(</span><span class="pln">make-term 
          </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">order t1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">order t2</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">mul </span><span class="opn">(</span><span class="pln">coeff t1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">coeff t2</span><span class="clo">)))</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">mul-term-by-all-terms 
          t1 
          </span><span class="opn">(</span><span class="pln">rest-terms L</span><span class="clo">))))))</span></pre></div>

<p>This is really all there is to polynomial addition and multiplication.  Notice
that, since we operate on terms using the generic procedures <code>add</code> and
<code>mul</code>, our polynomial package is automatically able to handle any type of
coefficient that is known about by the generic arithmetic package.  If we
include a coercion mechanism such as one of those discussed in 
<a href="#g_t2_002e5_002e2">2.5.2</a>, then we also are automatically able to handle operations on
polynomials of different coefficient types, such as
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">[</mo>
    <mn>3</mn>
    <msup>
      <mi>x</mi>
      <mn>2</mn>
    </msup>
    <mo>+</mo>
    <mo stretchy="false">(</mo>
    <mn>2</mn>
    <mo>+</mo>
    <mn>3</mn>
    <mi>i</mi>
    <mo stretchy="false">)</mo>
    <mi>x</mi>
    <mo>+</mo>
    <mn>7</mn>
    <mo stretchy="false">]</mo>
    <mo>⋅<!-- ⋅ --></mo>
  </mrow>
  <mrow class="MJX-TeXAtom-ORD">
    <mrow>
      <mo>[</mo>
      <msup>
        <mi>x</mi>
        <mn>4</mn>
      </msup>
      <mo>+</mo>
      <mrow class="MJX-TeXAtom-ORD">
        <mfrac>
          <mn>2</mn>
          <mn>3</mn>
        </mfrac>
      </mrow>
      <msup>
        <mi>x</mi>
        <mn>2</mn>
      </msup>
      <mo>+</mo>
      <mo stretchy="false">(</mo>
      <mn>5</mn>
      <mo>+</mo>
      <mn>3</mn>
      <mi>i</mi>
      <mo stretchy="false">)</mo>
      <mo>]</mo>
    </mrow>
    <mo>.</mo>
  </mrow>
</math>
Because we installed the polynomial addition and multiplication procedures
<code>add-poly</code> and <code>mul-poly</code> in the generic arithmetic system as the
<code>add</code> and <code>mul</code> operations for type <code>polynomial</code>, our system is
also automatically able to handle polynomial operations such as
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mrow class="MJX-TeXAtom-ORD">
      <mo maxsize="1.623em" minsize="1.623em">[</mo>
    </mrow>
    <mo stretchy="false">(</mo>
    <mi>y</mi>
    <mo>+</mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
    <msup>
      <mi>x</mi>
      <mn>2</mn>
    </msup>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <msup>
      <mi>y</mi>
      <mn>2</mn>
    </msup>
    <mo>+</mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
    <mi>x</mi>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>y</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
    <mrow class="MJX-TeXAtom-ORD">
      <mo maxsize="1.623em" minsize="1.623em">]</mo>
    </mrow>
    <mo>⋅<!-- ⋅ --></mo>
  </mrow>
  <mrow class="MJX-TeXAtom-ORD">
    <mrow class="MJX-TeXAtom-ORD">
      <mo maxsize="1.623em" minsize="1.623em">[</mo>
    </mrow>
    <mo stretchy="false">(</mo>
    <mi>y</mi>
    <mo>−<!-- − --></mo>
    <mn>2</mn>
    <mo stretchy="false">)</mo>
    <mi>x</mi>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <msup>
      <mi>y</mi>
      <mn>3</mn>
    </msup>
    <mo>+</mo>
    <mn>7</mn>
    <mo stretchy="false">)</mo>
    <mrow class="MJX-TeXAtom-ORD">
      <mo maxsize="1.623em" minsize="1.623em">]</mo>
    </mrow>
    <mo>.</mo>
  </mrow>
</math>
The reason is that when the system tries to combine coefficients, it will
dispatch through <code>add</code> and <code>mul</code>.  Since the coefficients are
themselves polynomials (in <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math>), these will be combined using <code>add-poly</code>
and <code>mul-poly</code>.  The result is a kind of “data-directed recursion” in
which, for example, a call to <code>mul-poly</code> will result in recursive calls to
<code>mul-poly</code> in order to multiply the coefficients.  If the coefficients of
the coefficients were themselves polynomials (as might be used to represent
polynomials in three variables), the data direction would ensure that the
system would follow through another level of recursive calls, and so on through
as many levels as the structure of the data dictates.<a class="footnote_link" id="DOCF123" href="#FOOT123"><sup>123</sup></a>
</p>
<a id="Representing-term-lists"></a>
<h5 class="subsubheading">Representing term lists</h5>

<p>Finally, we must confront the job of implementing a good representation for
term lists.  A term list is, in effect, a set of coefficients keyed by the
order of the term.  Hence, any of the methods for representing sets, as
discussed in <a href="2_002e3.xhtml#g_t2_002e3_002e3">2.3.3</a>, can be applied to this task.  On the other
hand, our procedures <code>add-terms</code> and <code>mul-terms</code> always access term
lists sequentially from highest to lowest order.  Thus, we will use some kind
of ordered list representation.
</p>
<p>How should we structure the list that represents a term list?  One
consideration is the “density” of the polynomials we intend to manipulate.  A
polynomial is said to be <a id="index-dense"></a>
<em>dense</em> if it has nonzero coefficients in
terms of most orders.  If it has many zero terms it is said to be
<a id="index-sparse"></a>
<em>sparse</em>.  For example,
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mi>A</mi>
  <mo>:</mo>
  <mspace width="1em"/>
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>x</mi>
      <mn>5</mn>
    </msup>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>2</mn>
    <msup>
      <mi>x</mi>
      <mn>4</mn>
    </msup>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>3</mn>
    <msup>
      <mi>x</mi>
      <mn>2</mn>
    </msup>
  </mrow>
  <mo>−<!-- − --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>2</mn>
    <mi>x</mi>
  </mrow>
  <mo>−<!-- − --></mo>
  <mn>5</mn>
</math>
is a dense polynomial, whereas
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mi>B</mi>
  <mo>:</mo>
  <mspace width="1em"/>
  <msup>
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mn>100</mn>
    </mrow>
  </msup>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>2</mn>
    <msup>
      <mi>x</mi>
      <mn>2</mn>
    </msup>
  </mrow>
  <mo>+</mo>
  <mn>1</mn>
</math>
is sparse.
</p>
<p>The term lists of dense polynomials are most efficiently represented as lists
of the coefficients.  For example, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>A</mi>
</math> above would be nicely represented as
<code>(1 2 0 3 -2 -5)</code>.  The order of a term in this representation is the
length of the sublist beginning with that term’s coefficient, decremented by
1.<a class="footnote_link" id="DOCF124" href="#FOOT124"><sup>124</sup></a>  This would be a terrible representation for
a sparse polynomial such as <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>B</mi>
</math>: There would be a giant list of zeros
punctuated by a few lonely nonzero terms.  A more reasonable representation of
the term list of a sparse polynomial is as a list of the nonzero terms, where
each term is a list containing the order of the term and the coefficient for
that order.  In such a scheme, polynomial <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>B</mi>
</math> is efficiently represented as
<code>((100 1) (2 2) (0 1))</code>.  As most polynomial manipulations are performed
on sparse polynomials, we will use this method.  We will assume that term lists
are represented as lists of terms, arranged from highest-order to lowest-order
term.  Once we have made this decision, implementing the selectors and
constructors for terms and term lists is straightforward:<a class="footnote_link" id="DOCF125" href="#FOOT125"><sup>125</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">adjoin-term term term-list</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln">zero? </span><span class="opn">(</span><span class="pln">coeff term</span><span class="clo">))</span><span class="pln">
      term-list
      </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> term term-list</span><span class="clo">)))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">the-empty-termlist</span><span class="clo">)</span><span class="pln"> </span><span class="lit">'</span><span class="opn">(</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">first-term term-list</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> term-list</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">rest-terms term-list</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> term-list</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">empty-termlist? term-list</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">null? term-list</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-term order coeff</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">list order coeff</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">order term</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> term</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">coeff term</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> term</span><span class="clo">))</span></pre></div>

<p>where <code>=zero?</code> is as defined in <a href="#Exercise-2_002e80">Exercise 2.80</a>.  (See also
<a href="#Exercise-2_002e87">Exercise 2.87</a> below.)
</p>
<p>Users of the polynomial package will create (tagged) polynomials by means of
the procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-polynomial var terms</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">get </span><span class="lit">'make</span><span class="pln"> </span><span class="lit">'polynomial</span><span class="clo">)</span><span class="pln"> var terms</span><span class="clo">))</span></pre></div>

<blockquote>
<p><strong><a id="Exercise-2_002e87"></a>Exercise 2.87:</strong> Install <code>=zero?</code> for
polynomials in the generic arithmetic package.  This will allow
<code>adjoin-term</code> to work for polynomials with coefficients that are
themselves polynomials.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e88"></a>Exercise 2.88:</strong> Extend the polynomial system to
include subtraction of polynomials.  (Hint: You may find it helpful to define a
generic negation operation.)
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e89"></a>Exercise 2.89:</strong> Define procedures that implement
the term-list representation described above as appropriate for dense
polynomials.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e90"></a>Exercise 2.90:</strong> Suppose we want to have a
polynomial system that is efficient for both sparse and dense polynomials.  One
way to do this is to allow both kinds of term-list representations in our
system.  The situation is analogous to the complex-number example of 
<a href="2_002e4.xhtml#g_t2_002e4">2.4</a>, where we allowed both rectangular and polar representations.  To do
this we must distinguish different types of term lists and make the operations
on term lists generic.  Redesign the polynomial system to implement this
generalization.  This is a major effort, not a local change.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e91"></a>Exercise 2.91:</strong> A univariate polynomial can be
divided by another one to produce a polynomial quotient and a polynomial
remainder.  For example,
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mrow>
        <msup>
          <mi>x</mi>
          <mn>5</mn>
        </msup>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mrow>
      <mrow>
        <msup>
          <mi>x</mi>
          <mn>2</mn>
        </msup>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mrow>
    </mfrac>
  </mrow>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>x</mi>
      <mn>3</mn>
    </msup>
    <mo>+</mo>
    <mi>x</mi>
    <mo>,</mo>
  </mrow>
  <mtext> remainder </mtext>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mo>−<!-- − --></mo>
    <mn>1.</mn>
  </mrow>
</math>
Division can be performed via long division.  That is, divide the highest-order
term of the dividend by the highest-order term of the divisor.  The result is
the first term of the quotient.  Next, multiply the result by the divisor,
subtract that from the dividend, and produce the rest of the answer by
recursively dividing the difference by the divisor.  Stop when the order of the
divisor exceeds the order of the dividend and declare the dividend to be the
remainder.  Also, if the dividend ever becomes zero, return zero as both
quotient and remainder.
</p>
<p>We can design a <code>div-poly</code> procedure on the model of <code>add-poly</code> and
<code>mul-poly</code>. The procedure checks to see if the two polys have the same
variable.  If so, <code>div-poly</code> strips off the variable and passes the
problem to <code>div-terms</code>, which performs the division operation on term
lists. <code>Div-poly</code> finally reattaches the variable to the result supplied
by <code>div-terms</code>.  It is convenient to design <code>div-terms</code> to compute
both the quotient and the remainder of a division.  <code>Div-terms</code> can take
two term lists as arguments and return a list of the quotient term list and the
remainder term list.
</p>
<p>Complete the following definition of <code>div-terms</code> by filling in the missing
expressions.  Use this to implement <code>div-poly</code>, which takes two polys as
arguments and returns a list of the quotient and remainder polys.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">div-terms L1 L2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">empty-termlist? L1</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">list </span><span class="opn">(</span><span class="pln">the-empty-termlist</span><span class="clo">)</span><span class="pln"> 
            </span><span class="opn">(</span><span class="pln">the-empty-termlist</span><span class="clo">))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">t1 </span><span class="opn">(</span><span class="pln">first-term L1</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">t2 </span><span class="opn">(</span><span class="pln">first-term L2</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;</span><span class="pln"> </span><span class="opn">(</span><span class="pln">order t2</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">order t1</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">list </span><span class="opn">(</span><span class="pln">the-empty-termlist</span><span class="clo">)</span><span class="pln"> L1</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">new-c </span><span class="opn">(</span><span class="pln">div </span><span class="opn">(</span><span class="pln">coeff t1</span><span class="clo">)</span><span class="pln"> 
                              </span><span class="opn">(</span><span class="pln">coeff t2</span><span class="clo">)))</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">new-o </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="opn">(</span><span class="pln">order t1</span><span class="clo">)</span><span class="pln"> 
                            </span><span class="opn">(</span><span class="pln">order t2</span><span class="clo">))))</span><span class="pln">
              </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">rest-of-result
                     ⟨</span><var><span class="pln">compute rest of result 
                     recursively</span></var><span class="pln">⟩ </span><span class="clo">))</span><span class="pln">
                ⟨</span><var><span class="pln">form complete result</span></var><span class="pln">⟩ </span><span class="clo">))))))</span></pre></div>
</blockquote>

<a id="Hierarchies-of-types-in-symbolic-algebra"></a>
<h5 class="subsubheading">Hierarchies of types in symbolic algebra</h5>

<p>Our polynomial system illustrates how objects of one type (polynomials) may in
fact be complex objects that have objects of many different types as parts.
This poses no real difficulty in defining generic operations.  We need only
install appropriate generic operations for performing the necessary
manipulations of the parts of the compound types.  In fact, we saw that
polynomials form a kind of “recursive data abstraction,” in that parts of a
polynomial may themselves be polynomials.  Our generic operations and our
data-directed programming style can handle this complication without much
trouble.
</p>
<p>On the other hand, polynomial algebra is a system for which the data types
cannot be naturally arranged in a tower.  For instance, it is possible to have
polynomials in <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> whose coefficients are polynomials in <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math>.  It is also
possible to have polynomials in <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math> whose coefficients are polynomials in
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math>.  Neither of these types is “above” the other in any natural way, yet
it is often necessary to add together elements from each set.  There are
several ways to do this.  One possibility is to convert one polynomial to the
type of the other by expanding and rearranging terms so that both polynomials
have the same principal variable.  One can impose a towerlike structure on this
by ordering the variables and thus always converting any polynomial to a
“canonical form” with the highest-priority variable dominant and the
lower-priority variables buried in the coefficients.  This strategy works
fairly well, except that the conversion may expand a polynomial unnecessarily,
making it hard to read and perhaps less efficient to work with.  The tower
strategy is certainly not natural for this domain or for any domain where the
user can invent new types dynamically using old types in various combining
forms, such as trigonometric functions, power series, and integrals.
</p>
<p>It should not be surprising that controlling coercion is a serious problem in
the design of large-scale algebraic-manipulation systems.  Much of the
complexity of such systems is concerned with relationships among diverse types.
Indeed, it is fair to say that we do not yet completely understand coercion.
In fact, we do not yet completely understand the concept of a data type.
Nevertheless, what we know provides us with powerful structuring and modularity
principles to support the design of large systems.
</p>
<blockquote>
<p><strong><a id="Exercise-2_002e92"></a>Exercise 2.92:</strong> By imposing an ordering on
variables, extend the polynomial package so that addition and multiplication of
polynomials works for polynomials in different variables.  (This is not easy!)
</p></blockquote>

<a id="Extended-exercise_003a-Rational-functions"></a>
<h5 class="subsubheading">Extended exercise: Rational functions</h5>

<p>We can extend our generic arithmetic system to include <a id="index-rational-functions"></a>
<em>rational functions</em>.  
These are “fractions” whose numerator and denominator are
polynomials, such as
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mrow class="MJX-TeXAtom-ORD">
      <mfrac>
        <mrow>
          <mi>x</mi>
          <mo>+</mo>
          <mn>1</mn>
        </mrow>
        <mrow>
          <msup>
            <mi>x</mi>
            <mn>3</mn>
          </msup>
          <mo>−<!-- − --></mo>
          <mn>1</mn>
        </mrow>
      </mfrac>
    </mrow>
    <mo>.</mo>
  </mrow>
</math>
The system should be able to add, subtract, multiply, and divide rational
functions, and to perform such computations as
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mrow>
        <mi>x</mi>
        <mo>+</mo>
        <mn>1</mn>
      </mrow>
      <mrow>
        <msup>
          <mi>x</mi>
          <mn>3</mn>
        </msup>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mrow>
    </mfrac>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mi>x</mi>
      <mrow>
        <msup>
          <mi>x</mi>
          <mn>2</mn>
        </msup>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mrow>
    </mfrac>
  </mrow>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mrow class="MJX-TeXAtom-ORD">
      <mfrac>
        <mrow>
          <msup>
            <mi>x</mi>
            <mn>3</mn>
          </msup>
          <mo>+</mo>
          <mn>2</mn>
          <msup>
            <mi>x</mi>
            <mn>2</mn>
          </msup>
          <mo>+</mo>
          <mn>3</mn>
          <mi>x</mi>
          <mo>+</mo>
          <mn>1</mn>
        </mrow>
        <mrow>
          <msup>
            <mi>x</mi>
            <mn>4</mn>
          </msup>
          <mo>+</mo>
          <msup>
            <mi>x</mi>
            <mn>3</mn>
          </msup>
          <mo>−<!-- − --></mo>
          <mi>x</mi>
          <mo>−<!-- − --></mo>
          <mn>1</mn>
        </mrow>
      </mfrac>
    </mrow>
    <mo>.</mo>
  </mrow>
</math>
(Here the sum has been simplified by removing common factors.  Ordinary “cross
multiplication” would have produced a fourth-degree polynomial over a
fifth-degree polynomial.)
</p>
<p>If we modify our rational-arithmetic package so that it uses generic
operations, then it will do what we want, except for the problem of reducing
fractions to lowest terms.
</p>
<blockquote>
<p><strong><a id="Exercise-2_002e93"></a>Exercise 2.93:</strong> Modify the rational-arithmetic
package to use generic operations, but change <code>make-rat</code> so that it does
not attempt to reduce fractions to lowest terms.  Test your system by calling
<code>make-rational</code> on two polynomials to produce a rational function:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> p1 </span><span class="opn">(</span><span class="pln">make-polynomial </span><span class="lit">'x</span><span class="pln"> </span><span class="lit">'</span><span class="opn">((</span><span class="lit">2</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="lit">0</span><span class="pln"> </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> p2 </span><span class="opn">(</span><span class="pln">make-polynomial </span><span class="lit">'x</span><span class="pln"> </span><span class="lit">'</span><span class="opn">((</span><span class="lit">3</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="lit">0</span><span class="pln"> </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> rf </span><span class="opn">(</span><span class="pln">make-rational p2 p1</span><span class="clo">))</span></pre></div>

<p>Now add <code>rf</code> to itself, using <code>add</code>. You will observe that this
addition procedure does not reduce fractions to lowest terms.
</p></blockquote>

<p>We can reduce polynomial fractions to lowest terms using the same idea we used
with integers: modifying <code>make-rat</code> to divide both the numerator and the
denominator by their greatest common divisor.  The notion of “greatest common
divisor” makes sense for polynomials.  In fact, we can compute the
<abbr>GCD</abbr> of two polynomials using essentially the same Euclid’s Algorithm
that works for integers.<a class="footnote_link" id="DOCF126" href="#FOOT126"><sup>126</sup></a>  The integer version is
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">gcd a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> b </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
      a
      </span><span class="opn">(</span><span class="pln">gcd b </span><span class="opn">(</span><span class="pln">remainder a b</span><span class="clo">))))</span></pre></div>

<p>Using this, we could make the obvious modification to define a <abbr>GCD</abbr>
operation that works on term lists:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">gcd-terms a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">empty-termlist? b</span><span class="clo">)</span><span class="pln">
      a
      </span><span class="opn">(</span><span class="pln">gcd-terms b </span><span class="opn">(</span><span class="pln">remainder-terms a b</span><span class="clo">))))</span></pre></div>

<p>where <code>remainder-terms</code> picks out the remainder component of the list
returned by the term-list division operation <code>div-terms</code> that was
implemented in <a href="#Exercise-2_002e91">Exercise 2.91</a>.
</p>
<blockquote>
<p><strong><a id="Exercise-2_002e94"></a>Exercise 2.94:</strong> Using <code>div-terms</code>, implement
the procedure <code>remainder-terms</code> and use this to define <code>gcd-terms</code> as
above.  Now write a procedure <code>gcd-poly</code> that computes the polynomial
<abbr>GCD</abbr> of two polys.  (The procedure should signal an error if the two
polys are not in the same variable.)  Install in the system a generic operation
<code>greatest-common-divisor</code> that reduces to <code>gcd-poly</code> for polynomials
and to ordinary <code>gcd</code> for ordinary numbers.  As a test, try
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> p1 
  </span><span class="opn">(</span><span class="pln">make-polynomial 
   </span><span class="lit">'x</span><span class="pln"> </span><span class="lit">'</span><span class="opn">((</span><span class="lit">4</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="lit">3</span><span class="pln"> </span><span class="lit">-1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="lit">2</span><span class="pln"> </span><span class="lit">-2</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> p2 
  </span><span class="opn">(</span><span class="pln">make-polynomial 
   </span><span class="lit">'x</span><span class="pln"> </span><span class="lit">'</span><span class="opn">((</span><span class="lit">3</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="lit">1</span><span class="pln"> </span><span class="lit">-1</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">greatest-common-divisor p1 p2</span><span class="clo">)</span></pre></div>

<p>and check your result by hand.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-2_002e95"></a>Exercise 2.95:</strong> Define <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>1</mn>
  </msub>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>2</mn>
  </msub>
</math>, and
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>3</mn>
  </msub>
</math> to be the polynomials
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtable columnalign="right left" rowspacing="4pt" columnspacing="1em">
    <mtr>
      <mtd>
        <msub>
          <mi>P</mi>
          <mn>1</mn>
        </msub>
        <mo>:</mo>
      </mtd>
      <mtd>
        <msup>
          <mi>x</mi>
          <mn>2</mn>
        </msup>
        <mo>−<!-- − --></mo>
        <mn>2</mn>
        <mi>x</mi>
        <mo>+</mo>
        <mn>1</mn>
        <mo>,</mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <msub>
          <mi>P</mi>
          <mn>2</mn>
        </msub>
        <mo>:</mo>
      </mtd>
      <mtd>
        <mn>11</mn>
        <msup>
          <mi>x</mi>
          <mn>2</mn>
        </msup>
        <mo>+</mo>
        <mn>7</mn>
        <mo>,</mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <msub>
          <mi>P</mi>
          <mn>3</mn>
        </msub>
        <mo>:</mo>
      </mtd>
      <mtd>
        <mn>13</mn>
        <mi>x</mi>
        <mo>+</mo>
        <mn>5.</mn>
      </mtd>
    </mtr>
  </mtable>
</math>
Now define <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>Q</mi>
    <mn>1</mn>
  </msub>
</math> to be the product of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>1</mn>
  </msub>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>2</mn>
  </msub>
</math>, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>Q</mi>
    <mn>2</mn>
  </msub>
</math> to be
the product of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>1</mn>
  </msub>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>3</mn>
  </msub>
</math>, and use <code>greatest-common-divisor</code>
(<a href="#Exercise-2_002e94">Exercise 2.94</a>) to compute the <abbr>GCD</abbr> of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>Q</mi>
    <mn>1</mn>
  </msub>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>Q</mi>
    <mn>2</mn>
  </msub>
</math>.
Note that the answer is not the same as <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>1</mn>
  </msub>
</math>.  This example introduces
noninteger operations into the computation, causing difficulties with the
<abbr>GCD</abbr> algorithm.<a class="footnote_link" id="DOCF127" href="#FOOT127"><sup>127</sup></a>  To understand what is happening, try tracing
<code>gcd-terms</code> while computing the <abbr>GCD</abbr> or try performing the
division by hand.
</p></blockquote>

<p>We can solve the problem exhibited in <a href="#Exercise-2_002e95">Exercise 2.95</a> if we use the
following modification of the <abbr>GCD</abbr> algorithm (which really works only
in the case of polynomials with integer coefficients).  Before performing any
polynomial division in the <abbr>GCD</abbr> computation, we multiply the dividend
by an integer constant factor, chosen to guarantee that no fractions will arise
during the division process.  Our answer will thus differ from the actual
<abbr>GCD</abbr> by an integer constant factor, but this does not matter in the
case of reducing rational functions to lowest terms; the <abbr>GCD</abbr> will be
used to divide both the numerator and denominator, so the integer constant
factor will cancel out.
</p>
<p>More precisely, if <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>P</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>Q</mi>
</math> are polynomials, let <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>O</mi>
    <mn>1</mn>
  </msub>
</math> be the order of
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>P</mi>
</math> (i.e., the order of the largest term of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>P</mi>
</math>) and let <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>O</mi>
    <mn>2</mn>
  </msub>
</math> be the
order of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>Q</mi>
</math>.  Let <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>c</mi>
</math> be the leading coefficient of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>Q</mi>
</math>.  Then it can be
shown that, if we multiply <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>P</mi>
</math> by the <a id="index-integerizing-factor"></a>
<em>integerizing<!-- /@w --> factor<!-- /@w --></em>
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>c</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mn>1</mn>
      <mo>+</mo>
      <msub>
        <mi>O</mi>
        <mn>1</mn>
      </msub>
      <mo>−<!-- − --></mo>
      <msub>
        <mi>O</mi>
        <mn>2</mn>
      </msub>
    </mrow>
  </msup>
</math>, the resulting polynomial can be divided by <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>Q</mi>
</math> by
using the <code>div-terms</code> algorithm without introducing any fractions.  The
operation of multiplying the dividend by this constant and then dividing is
sometimes called the <a id="index-pseudodivision"></a>
<em>pseudodivision</em> of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>P</mi>
</math> by <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>Q</mi>
</math>.  The remainder
of the division is called the <a id="index-pseudoremainder"></a>
<em>pseudoremainder</em>.
</p>
<blockquote>
<p><strong><a id="Exercise-2_002e96"></a>Exercise 2.96:</strong>
</p><ol>
<li> Implement the procedure <code>pseudoremainder-terms</code>, which is just like
<code>remainder-terms</code> except that it multiplies the dividend by the
integerizing factor described above before calling <code>div-terms</code>.  Modify
<code>gcd-terms</code> to use <code>pseudoremainder-terms</code>, and verify that
<code>greatest-common-divisor</code> now produces an answer with integer coefficients
on the example in <a href="#Exercise-2_002e95">Exercise 2.95</a>.

</li><li> The <abbr>GCD</abbr> now has integer coefficients, but they are larger than those
of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>P</mi>
    <mn>1</mn>
  </msub>
</math>.  Modify <code>gcd-terms</code> so that it removes common factors from the
coefficients of the answer by dividing all the coefficients by their (integer)
greatest common divisor.

</li></ol>
</blockquote>

<p>Thus, here is how to reduce a rational function to lowest terms:
</p>
<ul>
<li> Compute the <abbr>GCD</abbr> of the numerator and denominator, using the version
of <code>gcd-terms</code> from <a href="#Exercise-2_002e96">Exercise 2.96</a>.

</li><li> When you obtain the <abbr>GCD</abbr>, multiply both numerator and denominator by
the same integerizing factor before dividing through by the <abbr>GCD</abbr>, so
that division by the <abbr>GCD</abbr> will not introduce any noninteger
coefficients.  As the factor you can use the leading coefficient of the
<abbr>GCD</abbr> raised to the power <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>1</mn>
    <mo>+</mo>
    <msub>
      <mi>O</mi>
      <mn>1</mn>
    </msub>
    <mo>−<!-- − --></mo>
    <msub>
      <mi>O</mi>
      <mn>2</mn>
    </msub>
  </mrow>
</math>, where <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>O</mi>
    <mn>2</mn>
  </msub>
</math> is the
order of the <abbr>GCD</abbr> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>O</mi>
    <mn>1</mn>
  </msub>
</math> is the maximum of the orders of the
numerator and denominator.  This will ensure that dividing the numerator and
denominator by the <abbr>GCD</abbr> will not introduce any fractions.

</li><li> The result of this operation will be a numerator and denominator with integer
coefficients.  The coefficients will normally be very large because of all of
the integerizing factors, so the last step is to remove the redundant factors
by computing the (integer) greatest common divisor of all the coefficients of
the numerator and the denominator and dividing through by this factor.

</li></ul>

<blockquote>
<p><strong><a id="Exercise-2_002e97"></a>Exercise 2.97:</strong>
</p><ol>
<li> Implement this algorithm as a procedure <code>reduce-terms</code> that takes two term
lists <code>n</code> and <code>d</code> as arguments and returns a list <code>nn</code>,
<code>dd</code>, which are <code>n</code> and <code>d</code> reduced to lowest terms via the
algorithm given above.  Also write a procedure <code>reduce-poly</code>, analogous to
<code>add-poly</code>, that checks to see if the two polys have the same variable.
If so, <code>reduce-poly</code> strips off the variable and passes the problem to
<code>reduce-terms</code>, then reattaches the variable to the two term lists
supplied by <code>reduce-terms</code>.

</li><li> Define a procedure analogous to <code>reduce-terms</code> that does what the original
<code>make-rat</code> did for integers:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reduce-integers n d</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">g </span><span class="opn">(</span><span class="pln">gcd n d</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">list </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> n g</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> d g</span><span class="clo">))))</span></pre></div>

<p>and define <code>reduce</code> as a generic operation that calls <code>apply-generic</code>
to dispatch to either <code>reduce-poly</code> (for <code>polynomial</code> arguments) or
<code>reduce-integers</code> (for <code>scheme-number</code> arguments).  You can now
easily make the rational-arithmetic package reduce fractions to lowest terms by
having <code>make-rat</code> call <code>reduce</code> before combining the given numerator
and denominator to form a rational number.  The system now handles rational
expressions in either integers or polynomials.  To test your program, try the
example at the beginning of this extended exercise:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> p1 
  </span><span class="opn">(</span><span class="pln">make-polynomial </span><span class="lit">'x</span><span class="pln"> </span><span class="lit">'</span><span class="opn">((</span><span class="lit">1</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="lit">0</span><span class="pln"> </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> p2 
  </span><span class="opn">(</span><span class="pln">make-polynomial </span><span class="lit">'x</span><span class="pln"> </span><span class="lit">'</span><span class="opn">((</span><span class="lit">3</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="lit">0</span><span class="pln"> </span><span class="lit">-1</span><span class="clo">))))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> p3 
  </span><span class="opn">(</span><span class="pln">make-polynomial </span><span class="lit">'x</span><span class="pln"> </span><span class="lit">'</span><span class="opn">((</span><span class="lit">1</span><span class="pln"> </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> p4 
  </span><span class="opn">(</span><span class="pln">make-polynomial </span><span class="lit">'x</span><span class="pln"> </span><span class="lit">'</span><span class="opn">((</span><span class="lit">2</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="lit">0</span><span class="pln"> </span><span class="lit">-1</span><span class="clo">))))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> rf1 </span><span class="opn">(</span><span class="pln">make-rational p1 p2</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> rf2 </span><span class="opn">(</span><span class="pln">make-rational p3 p4</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">add rf1 rf2</span><span class="clo">)</span></pre></div>

<p>See if you get the correct answer, correctly reduced to lowest terms.
</p></li></ol>
</blockquote>

<p>The <abbr>GCD</abbr> computation is at the heart of any system that does
operations on rational functions.  The algorithm used above, although
mathematically straightforward, is extremely slow.  The slowness is due partly
to the large number of division operations and partly to the enormous size of
the intermediate coefficients generated by the pseudodivisions.  One of the
active areas in the development of algebraic-manipulation systems is the design
of better algorithms for computing polynomial <abbr>GCD</abbr>s.<a class="footnote_link" id="DOCF128" href="#FOOT128"><sup>128</sup></a>
</p>

<div class="footnote">
<h4 class="footnotes-heading">Footnotes</h4>

<div id="FOOT115"><p><a class="footnote_backlink" href="#DOCF115"><sup>115</sup></a>
We also have
to supply an almost identical procedure to handle the types
<code>(scheme-number complex)</code>.</p>
</div>
<div id="FOOT116"><p><a class="footnote_backlink" href="#DOCF116"><sup>116</sup></a>
See <a href="#Exercise-2_002e82">Exercise 2.82</a> for generalizations.</p>
</div>
<div id="FOOT117"><p><a class="footnote_backlink" href="#DOCF117"><sup>117</sup></a>
If we are clever, we can usually get by with fewer
than <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mn>2</mn>
  </msup>
</math> coercion procedures.  For instance, if we know how to convert from
type 1 to type 2 and from type 2 to type 3, then we can use this knowledge to
convert from type 1 to type 3.  This can greatly decrease the number of
coercion procedures we need to supply explicitly when we add a new type to the
system.  If we are willing to build the required amount of sophistication into
our system, we can have it search the “graph” of relations among types and
automatically generate those coercion procedures that can be inferred from the
ones that are supplied explicitly.</p>
</div>
<div id="FOOT118"><p><a class="footnote_backlink" href="#DOCF118"><sup>118</sup></a>
This statement,
which also appears in the first edition of this book, is just as true now as it
was when we wrote it twelve years ago.  Developing a useful, general framework
for expressing the relations among different types of entities (what
philosophers call “ontology”) seems intractably difficult.  The main
difference between the confusion that existed ten years ago and the confusion
that exists now is that now a variety of inadequate ontological theories have
been embodied in a plethora of correspondingly inadequate programming
languages.  For example, much of the complexity of object-oriented programming
languages—and the subtle and confusing differences among contemporary
object-oriented languages—centers on the treatment of generic operations on
interrelated types.  Our own discussion of computational objects in
<a href="Chapter-3.xhtml#Chapter-3">Chapter 3</a> avoids these issues entirely.  Readers familiar with
object-oriented programming will notice that we have much to say in
chapter 3 about local state, but we do not even mention “classes” or
“inheritance.”  In fact, we suspect that these problems cannot be adequately
addressed in terms of computer-language design alone, without also drawing on
work in knowledge representation and automated reasoning.</p>
</div>
<div id="FOOT119"><p><a class="footnote_backlink" href="#DOCF119"><sup>119</sup></a>
A real number can be projected to an integer using the
<code>round</code> primitive, which returns the closest integer to its argument.</p>
</div>
<div id="FOOT120"><p><a class="footnote_backlink" href="#DOCF120"><sup>120</sup></a>
On the other hand,
we will allow polynomials whose coefficients are themselves polynomials in
other variables.  This will give us essentially the same representational power
as a full multivariate system, although it does lead to coercion problems, as
discussed below.</p>
</div>
<div id="FOOT121"><p><a class="footnote_backlink" href="#DOCF121"><sup>121</sup></a>
For univariate polynomials, giving the value of a polynomial
at a given set of points can be a particularly good representation.  This makes
polynomial arithmetic extremely simple.  To obtain, for example, the sum of two
polynomials represented in this way, we need only add the values of the
polynomials at corresponding points.  To transform back to a more familiar
representation, we can use the Lagrange interpolation formula, which shows how
to recover the coefficients of a polynomial of degree <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> given the values of
the polynomial at <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>+</mo>
    <mn>1</mn>
  </mrow>
</math> points.</p>
</div>
<div id="FOOT122"><p><a class="footnote_backlink" href="#DOCF122"><sup>122</sup></a>
This operation is very much like the ordered
<code>union-set</code> operation we developed in <a href="2_002e3.xhtml#Exercise-2_002e62">Exercise 2.62</a>.  In
fact, if we think of the terms of the polynomial as a set ordered according to
the power of the indeterminate, then the program that produces the term list
for a sum is almost identical to <code>union-set</code>.</p>
</div>
<div id="FOOT123"><p><a class="footnote_backlink" href="#DOCF123"><sup>123</sup></a>
To make this
work completely smoothly, we should also add to our generic arithmetic system
the ability to coerce a “number” to a polynomial by regarding it as a
polynomial of degree zero whose coefficient is the number.  This is necessary
if we are going to perform operations such as
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">[</mo>
    <msup>
      <mi>x</mi>
      <mn>2</mn>
    </msup>
    <mo>+</mo>
    <mo stretchy="false">(</mo>
    <mi>y</mi>
    <mo>+</mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
    <mi>x</mi>
    <mo>+</mo>
    <mn>5</mn>
    <mo stretchy="false">]</mo>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">[</mo>
    <msup>
      <mi>x</mi>
      <mn>2</mn>
    </msup>
    <mo>+</mo>
    <mn>2</mn>
    <mi>x</mi>
    <mo>+</mo>
    <mn>1</mn>
    <mo stretchy="false">]</mo>
    <mo>,</mo>
  </mrow>
</math>
which requires adding the coefficient <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo>+</mo>
    <mn>1</mn>
  </mrow>
</math> to the coefficient 2.</p>
</div>
<div id="FOOT124"><p><a class="footnote_backlink" href="#DOCF124"><sup>124</sup></a>
In these polynomial examples, we assume that we have implemented
the generic arithmetic system using the type mechanism suggested in
<a href="#Exercise-2_002e78">Exercise 2.78</a>.  Thus, coefficients that are ordinary numbers will be
represented as the numbers themselves rather than as pairs whose <code>car</code> is
the symbol <code>scheme-number</code>.</p>
</div>
<div id="FOOT125"><p><a class="footnote_backlink" href="#DOCF125"><sup>125</sup></a>
Although we
are assuming that term lists are ordered, we have implemented
<code>adjoin-term</code> to simply <code>cons</code> the new term onto the existing term
list.  We can get away with this so long as we guarantee that the procedures
(such as <code>add-terms</code>) that use <code>adjoin-term</code> always call it with a
higher-order term than appears in the list.  If we did not want to make such a
guarantee, we could have implemented <code>adjoin-term</code> to be similar to the
<code>adjoin-set</code> constructor for the ordered-list representation of sets
(<a href="2_002e3.xhtml#Exercise-2_002e61">Exercise 2.61</a>).</p>
</div>
<div id="FOOT126"><p><a class="footnote_backlink" href="#DOCF126"><sup>126</sup></a>
The fact that Euclid’s Algorithm works for
polynomials is formalized in algebra by saying that polynomials form a kind of
algebraic domain called a <a id="index-Euclidean-ring"></a>
<em>Euclidean ring</em>.  A Euclidean ring is a
domain that admits addition, subtraction, and commutative multiplication,
together with a way of assigning to each element <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> of the ring a positive
integer “measure” <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>m</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> with the properties that 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>m</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mi>y</mi>
    <mo stretchy="false">)</mo>
    <mo>≥<!-- ≥ --></mo>
    <mi>m</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> for any nonzero <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math> and that, given any <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> and
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math>, there exists a <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>q</mi>
</math> such that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo>=</mo>
    <mi>q</mi>
    <mi>x</mi>
    <mo>+</mo>
    <mi>r</mi>
  </mrow>
</math> and either
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>r</mi>
    <mo>=</mo>
    <mn>0</mn>
  </mrow>
</math> or <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>m</mi>
    <mo stretchy="false">(</mo>
    <mi>r</mi>
    <mo stretchy="false">)</mo>
    <mo>&lt;</mo>
    <mi>m</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  From an abstract point of view, this
is what is needed to prove that Euclid’s Algorithm works.  For the domain of
integers, the measure <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>m</mi>
</math> of an integer is the absolute value of the integer
itself.  For the domain of polynomials, the measure of a polynomial is its
degree.</p>
</div>
<div id="FOOT127"><p><a class="footnote_backlink" href="#DOCF127"><sup>127</sup></a>
In an implementation like <abbr>MIT</abbr>
Scheme, this produces a polynomial that is indeed a divisor of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>Q</mi>
    <mn>1</mn>
  </msub>
</math> and
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>Q</mi>
    <mn>2</mn>
  </msub>
</math>, but with rational coefficients.  In many other Scheme systems, in
which division of integers can produce limited-precision decimal numbers, we
may fail to get a valid divisor.</p>
</div>
<div id="FOOT128"><p><a class="footnote_backlink" href="#DOCF128"><sup>128</sup></a>
One
extremely efficient and elegant method for computing polynomial <abbr>GCD</abbr>s
was discovered by Richard <a href="References.xhtml#Zippel-_00281979_0029">Zippel (1979)</a>.  The method is a probabilistic
algorithm, as is the fast test for primality that we discussed in <a href="Chapter-1.xhtml#Chapter-1">Chapter 1</a>.  Zippel’s book (<a href="References.xhtml#Zippel-1993">Zippel 1993</a>) describes this method, together with other ways to
compute polynomial <abbr>GCD</abbr>s.</p>
</div>
</div>
<nav class="header">
<p>
Next: <a href="Chapter-3.xhtml#Chapter-3" accesskey="n" rel="next">Chapter 3</a>, Prev: <a href="2_002e4.xhtml#g_t2_002e4" accesskey="p" rel="prev">2.4</a>, Up: <a href="#g_t2_002e5" accesskey="u" rel="prev">2.5</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>


</section><span class="bottom jump" title="Jump to bottom"><a href="#pagebottom" accesskey="b">⇣</a></span><a id="pagebottom"></a>
</body>
</html>